/**
 * 2分查找，切割数组有消耗，待优化
 * O(log n)
 * @param {*} sortedArr 
 * @param {*} item 
 * @param {*} pre 
 * @returns 
 */
function BinarySearch1(sortedArr,item,pre=0){
    console.log(sortedArr)
    if(!sortedArr.length){
        return ;
    }
    let midIndex=sortedArr.length/2;
    if(sortedArr.length%2!==0){
        midIndex=Math.floor(midIndex)
    }
    // console.log(item,sortedArr[midIndex])
    if(item===sortedArr[midIndex]){
        
        return midIndex+pre
    }else if(item>sortedArr[midIndex]){
        return BinarySearch(sortedArr.slice(midIndex),item,pre+midIndex)
    }else{
        return BinarySearch(sortedArr.slice(0,midIndex),item,pre)
    }
}


/**
 * 2分查找，通过开始和结束指针
 * @param {*} sortedArr 
 * @param {*} item 
 * @param {*} pre 
 * @returns 
 */
function BinarySearch(sortedArr,item,start=0,end=sortedArr.length){
    console.log(sortedArr.slice(start,end),start,end)

    // 没有东西找了
    if(start===end){
        return -1;
    }
    let length=end-start;
    let midIndex=length/2;
    if(length%2!==0){
        midIndex=start+Math.floor(midIndex)
    }
    // console.log(item,sortedArr[midIndex])
    // 找到了
    if(item===sortedArr[midIndex]){
        return midIndex
    }else if(item>sortedArr[midIndex]){
        return BinarySearch(sortedArr,item,midIndex+1,end)
    }else{
        return BinarySearch(sortedArr,item,start,midIndex)
    }
}
console.log(BinarySearch([1,3,5],1))

